package com.hh.TreeQuestions;



/**
 * @author hanghao
 * @date 2023/8/3 22:29
 * 二叉树中的最大路径和
 * hard
 */
public class No124 {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(0, maxGain(root.left));
        int rightGain = Math.max(0, maxGain(root.right));
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int sum = root.val + leftGain + rightGain;
        //更新结果
        maxSum = Math.max(maxSum, sum);
        // 返回节点的最大贡献值
        return root.val + Math.max(leftGain,rightGain);
    }


    /**
     * 有个老哥的评论很棒，所以留下来了
     * 总的来说分成两点：①每个结点对上层的作用，②到每个结点的地方的时候，这件事儿能不能做的更好
     *
     * 这道题说难也不难，但说容易也真不是那么容易能想到的（写得比较多，但都是心得，耐心看完就更上一层楼了）。
     * 首先就是递归的方式，很多人都对递归一头雾水，一看就会，一写就废。不用担心，这是正常现象。
     * 下面，我们详细解释一下这道题，顺便疏通一下递归的基本思路。
     *
     * 我们不要先去考虑整个递归的代码怎么去写，而是要明确一个递归的主体，就是这个递归的主体要怎么构造，然后再去想边界条件，
     * 返回值等等。
     * 1、那么，首先我们可以假设走到了某个节点，现在要面临的问题是路径的最大值问题，显然对于这种问题，每遍历到一个节点，我
     * 们都要求出包含该节点在内的此时的最大路径，并且在之后的遍历中更新这个最大值。对于该节点来说，它的最大路径currpath就
     * 等于左右子树的最大路径加上本身的值，也就是currpath = left+right+node,val，但是有一个前提，我们要求的是最大路
     * 径，所以若是left或者right小于等于0了，那么我们就没有必要把这些值加上了，因为加上一个负数，会使得最大路径变小。这里
     * 的最大路径中的最其实就是一个限定条件，也就是我们常说的贪心算法，只取最大，最好，其余的直接丢弃。
     * 2、好了，1中的主体我们已经明确了，但是还存在一个问题，那就是left和right具体应该怎么求，也就是left和right的递归形
     * 式。显然我们要把node.left和node.right再次传输到递归函数中，重复上述的操作。但如果到达了叶子节点，是不是需要往上一
     * 层返回了呢？那么返回值又是多少呢？ 我们要明确left和right的基本含义，它们表示的是最大贡献，那么一个节点的最大贡献就
     * 等于node.val+max(left,right)，这个节点本身选上，然后从它的左右子树中选择最大的那个加上。 对于叶子节点也是这样，
     * 但是叶子节点的左右子树都为空，所以加上0，哎，注意看，此时是不是边界条件也出来了，但节点为空时，返回0 。 好了，至此循
     * 环的主体，返回值，边界条件都定义好了，那么整个递归的代码是不是就水到渠成了。这样一看递归也没什么了不起的！！！
     */
}
